package com.origin.niuke.greedy;

import java.util.Arrays;

/**
 * 主持人调度（二）
 * 有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，
 * 第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。
 * 一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动
 * ，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。
 * 求为了成功举办这 n 个活动，最少需要多少名主持人。
 * 算法：贪心、优先队列
 *
 * @author yezh
 * @date 2023/2/20 8:00
 */
public class NC147 {

    public int minmumNumberOfHost(int n, int[][] startEnd) {
        // write code here
        int[] start = new int[n], end = new int[n];
        for (int i = 0; i < n; i++) {
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int ans = 0;
        for (int i = 0, j = 0; i < n; i++) {
            if (start[i] < end[j]) ++ans;
            else ++j;
        }
        return ans;
    }

}
